package leetcode.editor.cn.q1_300.q150;

import java.util.Arrays;

/**
 * @author qidi
 * @date 2022-02-11 10:40:42
 */
class Q0174_DungeonGame {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int m = dungeon.length;
            int n = dungeon[0].length;

            // 骑士到 i、j 需要的最少血量
            int[][] mins = new int[m + 1][n + 1];

            for (int i = 0; i <= m; i++) {
                Arrays.fill(mins[i], Integer.MAX_VALUE);
            }

            mins[m - 1][n] = mins[m][n - 1] = 1;

            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    int cur = Math.min(mins[i + 1][j], mins[i][j + 1]);
                    mins[i][j] = Math.max(cur - dungeon[i][j], 1);
                }
            }

            return mins[0][0];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0174_DungeonGame().new Solution();
        System.out.println(solution.calculateMinimumHP(new int[][]{
                {0, -3}
        }));
        System.out.println(solution.calculateMinimumHP(new int[][]{
                {0, 5},
                {-2, -3},
        }));
        System.out.println(solution.calculateMinimumHP(new int[][]{
                {-2, -3, 3},
                {-5, -10, 1},
                {10, 30, -5},
        }));
    }
}